In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual of G, then G is a dual of H (if G is connected). The same notion of duality may also be used for more general embeddings of graphs on manifolds.
Contents |
Because of the dualism, any result involving counting regions and vertices can be dualized by exchanging them.
Let G be a connected graph. An algebraic dual of G is a graph G★ so that G and G★ have the same set of edges, any cycle of G is a cut of G★, and any cut of G is a cycle of G★. Every planar graph has an algebraic dual which is in general not unique (any dual defined by a plane embedding will do). The converse is actually true, as settled by Whitney:[2]
The same fact can be expressed in the theory of matroids: if M is the graphic matroid of a graph G, then the dual matroid of M is a graphic matroid if and only if G is planar. If G is planar, the dual matroid is the graphic matroid of the dual graph of G.
The weak dual of an embedded planar graph is the subgraph of the dual graph whose vertices correspond to the bounded faces of the primal graph. A planar graph is outerplanar if and only if its weak dual is a forest, and a planar graph is a Halin graph if and only if its weak dual is biconnected and outerplanar. For any embedded planar graph G, let G+ be the multigraph formed by adding a single new vertex v in the unbounded face of G, and connecting v to each vertex of the outer face (multiple times, if a vertex appears multiple times on the boundary of the outer face); then, G is the weak dual of the planar dual of G+.[3][4]